import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 739. Daily Temperatures 每日温度
 * https://leetcode.com/problems/daily-temperatures/description/
 */
class DailyTemperatures {
    /**
     * 方法：使用单调栈解决每日温度问题。维护一个存储索引的单调递减栈，当遇到更高温度时，计算天数差并更新结果数组。
     * 
     * Args:
     *   temperatures: int[] - 每日温度数组
     * 
     * Returns:
     *   int[] - 每个位置需要等待多少天才能遇到更高温度
     * 
     * Time: O(n) - 每个元素最多被压入和弹出栈一次
     * Space: O(n) - 最坏情况下栈的大小为n
     */
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n];
        Deque<Integer> st = new ArrayDeque<>();
        for(int i = 0; i < n; i++){
            int t = temperatures[i];
            while(!st.isEmpty() && t > temperatures[st.peek()]){
                int j = st.pop();
                ans[j] = i - j;
            }
            st.push(i);
        }
        return ans;
    }

    /**
     * 方法：使用单调栈从后向前遍历解决每日温度问题。维护一个存储索引的单调递减栈，当遇到更高温度时，计算天数差并更新结果数组。
     * 
     * Args:
     *   temperatures: int[] - 每日温度数组
     * 
     * Returns:
     *   int[] - 每个位置需要等待多少天才能遇到更高温度
     * 
     * Time: O(n) - 每个元素最多被压入和弹出栈一次
     * Space: O(n) - 最坏情况下栈的大小为n
     */
    public int[] dailyTemperatures1(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n];
        Deque<Integer> st = new ArrayDeque<>();
        for(int i = n - 1; i >= 0; i--){
            int t = temperatures[i];
            while(!st.isEmpty() && t >= temperatures[st.peek()]){
                st.pop();
            }
            if(!st.isEmpty()){
                ans[i] = st.peek() - i;
            }
            st.push(i);
        }
        return ans;
    }
}